package leetcode.strings;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
 * <p>
 * 示例 1：
 * <p>
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba"也是一个有效答案。
 * 示例 2：
 * <p>
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class Solution6 {
    public String longestPalindrome(String s) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < s.toCharArray().length; i++) {
            char c = s.charAt(i);
            int start = i;
            int end = s.lastIndexOf(c);
            String sub = s;
            while (start <= end) {
                if (start == end) {
                    res.add(c + "");
                    break;
                } else {
                    sub = sub.substring(start, end + 1);
                    boolean isrev = isrev(sub);
                    if (isrev) {
                        res.add(sub);
                        break;
                    } else {
                        end = sub.substring(0, end).lastIndexOf(c);
                        start = 0;
                    }
                }
            }
        }
        System.out.println(res);
        String result = "";
        for (String re : res) {
            if (re.length() > result.length()) {
                result = re;
            }
        }
        return result;
    }

    private boolean isrev(String s) {
        int start = 0;
        int end = s.length() - 1;
        boolean isrev = true;
        while (start <= end) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else {
                isrev = false;
                break;
            }
        }
        return isrev;
    }


    public static void main(String[] args) {
        //System.out.println(new Solution6().isrev("ddtattarrattatdd"));
        System.out.println(new Solution6().longestPalindrome("babaddtattarrattatddetartrateedredividerb"));
    }
}
